<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>利用“剪叶子”算法实现树形结构的搜索功能(深度遍历)</title>
  <script src="./treeData.js"></script>
</head>

<body>
  <script>
    let myTreeData = JSON.parse(JSON.stringify(treeData));
    // 重的
    function searchData(searchText = "") {
      // if (searchText === "") return;
      // 遍历,搜索顶层节点
      myTreeData.length > 0 && myTreeData.forEach((node) => {
        searchEach(node, searchText)
      })

      // 没有叶子节点的根节点也要清理掉(用来删除顶层节点)
      let length = myTreeData.length;
      for (let i = length - 1; i >= 0; i--) {
        let e2 = myTreeData[i];
        if (!isHasChildren(e2) && e2.name.indexOf(searchText) <= -1) {
          myTreeData.splice(i, 1);
        }
      }
      console.log(myTreeData)
    }

    // 对子节点进行搜索。
    function searchEach(node, value) {
      let depth = getTreeDepth(node);
      // 逐层遍历,
      for (let i = 0; i < depth - 1; i++) {
        // 记录【删除不匹配搜索内容的叶子节点】操作的次数。
        // 如果这个变量记录的操作次数为0，表示树形结构中，所有的 叶子节点(不包含只有根节点的情况)都匹配搜索内容。那么就没有必要再 在循环体里面遍历树了.
        let spliceCounter = 0;

        // 遍历树形结构
        traverseTree(node, n => {
          if (isHasChildren(n)) {
            let children = n.children;
            let length = children.length;

            // 找到不匹配搜索内容的叶子节点(该子节点无其他子节点)并删除。为了避免要删除的元素在数组中的索引改变，从后向前循环,
            for (let j = length - 1; j >= 0; j--) {
              let nowNode = children[j];
              if (!isHasChildren(nowNode) && nowNode.name.indexOf(value) <= -1) {
                children.splice(j, 1);
                spliceCounter++;
                console.log('======', spliceCounter, n)
              }
            }
            // console.log('=====', n)
          }
          // console.log('=====', n)
        })


        // 所有的叶子节点都匹配搜索内容，没必要再执行循环体了。
        if (spliceCounter == 0) {
          break;
        }
      }
    }

    // 判断树形结构中的一个节点是否具有孩子节点
    function isHasChildren(node) {
      let flag = false;
      if (node.children && node.children.length > 0) {
        flag = true;
      }
      return flag;
    }

    // 通过传入根节点获得树的深度，是 calDepth 的调用者。
    function getTreeDepth(node) {
      if (undefined == node || null == node) {
        return 0;
      }
      // 返回结果
      let r = 0;
      // 树中当前层节点的集合。
      let currentLevelNodes = [node];
      // 判断当前层是否有节点
      while (currentLevelNodes.length > 0) {
        // 当前层有节点，深度可以加一。
        r++;
        // 下一层节点的集合。
        let nextLevelNodes = new Array();
        // 找到树中所有的下一层节点，并把这些节点放到 nextLevelNodes 中。
        for (let i = 0; i < currentLevelNodes.length; i++) {
          let e = currentLevelNodes[i];
          if (isHasChildren(e)) {
            nextLevelNodes = nextLevelNodes.concat(e.children);
          }
        }
        // 令当前层节点集合的引用指向下一层节点的集合。
        currentLevelNodes = nextLevelNodes;
      }
      return r;
    }

    // 非递归遍历树(深度遍历), callback:当前节点
    function traverseTree(node, callback) {
      if (!node) { return; }
      var stack = [];
      stack.push(node);
      var tmpNode;
      // 逐个stack塞入, 删除; 一层一层遍历
      while (stack.length > 0) {
        tmpNode = stack.pop();
        callback(tmpNode); // 返回当前层数据
        if (tmpNode.children && tmpNode.children.length > 0) {
          for (let i = tmpNode.children.length - 1; i >= 0; i--) {
            stack.push(tmpNode.children[i]);
          }
        }
      }
    }

    // console.log(getTreeDepth({ children: treeData }))
    console.log(searchData('书'), myTreeData, treeData)
  </script>
</body>

</html>